package bit;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: bit
 * @Author: elvis
 * @CreateTime: 2020-09-30 16:24
 * @Description: 整数替换
 * 给定一个正整数 n，你可以做如下操作：
 *
 * 1. 如果 n 是偶数，则用 n / 2替换 n。
 * 2. 如果 n 是奇数，则可以用 n + 1或n - 1替换 n。
 * n 变为 1 所需的最小替换次数是多少？
 *
 * 示例 1:
 *
 * 输入:
 * 8
 *
 * 输出:
 * 3
 *
 * 解释:
 * 8 -> 4 -> 2 -> 1
 * 示例 2:
 *
 * 输入:
 * 7
 *
 * 输出:
 * 4
 *
 * 解释:
 * 7 -> 8 -> 4 -> 2 -> 1
 * 或
 * 7 -> 6 -> 3 -> 2 -> 1
 */
public class Leetcode397 {

    /**
     * 偶数直接右移，只有一种选项
     * 奇数+1或者-1，有两种选项。
     * 2.1 显然，让每一步1的数目最少好处大，于是 0bxxx01 采用 -1； 0bxxx11 采用 +1；
     * 2.2 特殊情况 3，按上述原则+1后两次右移共需3次；减一后只需一次右移共2次，因此3采用-1操作
     */
    public int integerReplacement(int n) {
        int count = 0;
        while (n != 1) {
            //与运算判断最后一位来区分奇偶
            if ((n & 1) == 0) {
                //偶数直接无符号右移，
                //2147483647 会被奇数处理算法加一溢出为负数，
                //若选用带符号右移将无法回到1.
                n >>>= 1;
            } else {
                //识别奇数的上一位是否为1，即 以 10 结尾(xxxx01)还是以11结尾(xxxx11)
                if ((n & 2) == 0 || n == 3) {
                    //01结尾最优则应当 用 n -1 取代 n
                    n -= 1;
                } else {
                    //11结尾除3这个特殊情况外，其余选用 n + 1取代 n，原因如上
                    n += 1;
                }
            }
            count++;
        }
        return count;
    }
}
